/**
*  妈的不写了，自己看JAVA版代码
 *
 * //基数排序，也叫桶排序
    public static void radixSort(int[] arr) {
        //第一步求数组中最大值的位数
        int maxNum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (maxNum < arr[i]) {
                maxNum = arr[i];
            }
        }
        int numDigits = (maxNum + "").length();

        //第二部设置循环达到递进取模
        int[][] barrel = new int[10][arr.length];//定义桶
        int[] barrelNum = new int[10];//定义数组存储桶里的有效数据
        int turnNum;//用于存放取模后的数的临时变量
        int index;//用于第四步
        for (int i = 0,n=1; i <numDigits; i++,n=n*10) {

            //第三步遍历数组，并将数组里的数取模存储到桶里
            for (int j = 0; j < arr.length; j++) {
                turnNum = arr[j] / (n) % 10;
                barrel[turnNum][barrelNum[turnNum]] = arr[j];//***值得注意
                barrelNum[turnNum]++;//这个数组中存放的本来就是桶中的数量
            }

            //第四步,按桶的顺序将桶中数据放回原数组
            index = 0;//用于充当arr的下标，来保证arr被重新赋值
            for (int j = 0; j < barrel.length; j++) {
                if (barrelNum[j] != 0) {
                    for (int k = 0; k < barrelNum[j]; k++) {
                        arr[index++] = barrel[j][k];
                    }
                }
                barrelNum[j] = 0;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

 *
 *
*/
//
// Created by 123 on 2024/4/1.
//
/**
 * 简单选择排序
 *      每次挑选最小的元素放在初始位置
 *          把大于中轴数据的放在 high的右边
 *          把小于中轴数据的放在 low的左边
 *     更新 n 轮最小位置
 *     即成
 *
 *      O(log n)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);


void radix_sort(Arr &arr);


int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    radix_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void radix_sort(Arr &arr) {
    int maxNum=-1;
    for (int i = 0; i < arr->length; ++i) {
        maxNum=maxNum<arr->data[i]?arr->data[i]:maxNum;
    }
    int numDigits=to_string(maxNum).length();
    //第二部设置循环达到递进取模
    int barrel[10][arr->length];//定义桶
    int barrelNum[10];//定义数组存储桶里的有效数据
    for (int i = 0; i < 10; ++i) {
        barrelNum[i]=0;
    }
    int turnNum;//用于存放取模后的数的临时变量
    int index;//用于第四步
    for (int i = 0 , n=1; i < numDigits; ++i,n=n*10) {
        for (int j = 0; j < arr->length; ++j) {
            turnNum=arr->data[j]/(n)%10;
            barrel[turnNum][barrelNum[turnNum]]=arr->data[j];
            barrelNum[turnNum]++;
        }
        index=0;
        for (int j = 0; j < 10; ++j) {
            if(barrelNum[j]==0)
                continue;
            for (int k = 0; k < barrelNum[j]; ++k) {
                arr->data[index++]=barrel[j][k];
            }
            barrelNum[j] = 0;
        }
    }
}


Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}

